package com.jwetherell.my.sort;

import com.jwetherell.my.Utils;

/**
 * Worst-case: O(n2) Average-case: O(n log n) Best-case: O(n log n)
 * 
 * Complexity Analysis: If the array contains n elements then the first run will
 * need O(n). In the best case, it will divide the array into almost two
 * identical parts. So sorting the remaining two sub-arrays takes 2 * O(n/2).
 * This ends up in a performance of O(n log n).
 * 
 * In worst case, it selects only one element in each iteration. So it is O(n) +
 * O(n-1) + (On-2).. O(1) which is equal to O(n^2).
 * 
 * @author yatendra
 * 
 */
public class QuickSort {

	public static void sort(int[] data) {
		quickSort(data, 0, data.length - 1);
	}

	private static void quickSort(int[] data, int low, int high) {
		/**
		 * sort only if the data contains at least two elements
		 */
		if (low < high) {

			int pivotIndex = Utils.partition(data, low, high);

			if (low < pivotIndex - 1) // If left-sublist size is > 1
				quickSort(data, low, pivotIndex - 1);

			if (pivotIndex + 1 < high) // If right-sublist size is > 1
				quickSort(data, pivotIndex + 1, high);
		}
	}

}